#include <bits/stdc++.h>

using namespace std;

// 子矩阵最大累加和问题
// 给定一个二维数组grid，找到其中子矩阵的最大累加和
// 返回拥有最大累加和的子矩阵左上角和右下角坐标
// 如果有多个子矩阵都有最大累加和，返回哪一个都可以
// 测试链接 : https://leetcode.cn/problems/max-submatrix-lcci/

class Solution 
{
public:
    // 如果行和列的规模都是n，时间复杂度O(n^3)，最优解了
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) 
    {
        int mx = INT_MIN;
        int a = 0, b = 0, c = 0, d = 0;
        int m = matrix.size(), n = matrix[0].size();
        int nums[n];
        for(int up = 0; up < m; ++up)
        {
            // nums[i] : matrix[up][i] ... matrix[down][i] 的和
            memset(nums, 0, sizeof(nums));
            for(int down = up; down < m; ++down)
            {
                // 如下代码就是题目1的附加问题 :
				// 子数组中找到拥有最大累加和的子数组
                for(int l = 0, r = 0, pre = INT_MIN; r < n; ++r)
                {
                    nums[r] += matrix[down][r];
                    if(pre >= 0) pre += nums[r];
                    else pre = nums[r], l = r;
                    if(pre > mx)
                    {
                        mx = pre;
                        a = up;
                        b = l;
                        c = down;
                        d = r;
                    }
                }
            }
        }

        return {a, b, c, d};
    }
};